698. Partition to K Equal Sum Subsets
📑 目录
题目 698. Partition to K Equal Sum Subsets
思路分析
代码实现
import java.util.Arrays;
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for (int num : nums) sum += num;
if (sum % k != 0) return false;
int target = sum / k;
Arrays.sort(nums);
if (nums[nums.length - 1] > target) return false;
boolean[] used = new boolean[nums.length];
return backtrack(nums, k, 0, nums.length - 1, 0, target, used);
}
// k: 还需要拼凑多少个桶
// curBucketSum: 当前桶已经装了多少
// start: 从nums的哪个索引开始尝试(避免重复枚举)
private boolean backtrack(int[] nums, int k, int curBucketSum, int start, int count, int target, boolean[] used) {
// base case: 如果 k 个桶都装满了（实际上只需要装满 k-1 个，最后一个自然就满了）
// 这里写 k==0 或者 k==1 都可以作为终止条件
if (k == 0) return true;
// 如果当前桶装满了，开始装下一个桶 (k-1)，重置 sum 和 start
if (curBucketSum == target) {
return backtrack(nums, k - 1, 0, nums.length - 1, 0, target, used);
}
for (int i = start; i >= 0; i--) {
if (used[i] || curBucketSum + nums[i] > target) continue;
used[i] = true;
if (backtrack(nums, k, curBucketSum + nums[i], i - 1, count + 1, target, used)) {
return true;
}
used[i] = false;
// --- 核心剪枝 (Pruning) ---
// 1. 如果当前桶是空的，且尝试放入 nums[i] 失败了。
// 说明 nums[i] 无法作为任何一个新桶的开头（因为所有空桶都是等价的）。
// 既然它无论如何都放不进新桶，那整个问题无解，直接剪枝。
if (curBucketSum == 0) return false;
// 2. 如果当前桶加上 nums[i] 恰好满了，但后续递归失败了。
// 说明 nums[i] 虽然能凑成 target，但会导致剩下的数字无解。
// 由于这是凑成 target 的最后一步，没有比这更完美的情况了，没必要试更小的数，直接剪枝。
if (curBucketSum + nums[i] == target) return false;
// 3. 去重剪枝：如果当前数字和前一个数字相同，且前一个数字没被用过（说明前一个数字刚才试过失败了）
// 那当前数字肯定也失败，跳过。
while (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
i--;
}
}
return false;
}
}
💬 评论